package algorthm.systemTraning.linkedList;


import java.security.Signature;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.atomic.LongAdder;

/**
 * @className: DeleteSpecialNumberInLinkedList
 * @Description: 删除链表中指定的值
 * @Author: wangyifei
 * @Date: 2022/9/2 17:31
 */
public class DeleteSpecialNumberInLinkedList {
    public static SingleNode deleteSingleLinkedList(SingleNode head , int special){
        SingleNode pre = null ;
        SingleNode next = head;
        while(next != null){
           if(next.getValue() == special){
               if(next == head){
                    head = next.getNext();
               }
               if(pre != null){
                   pre.setNext(next.getNext());
               }
               // 如何节点的值不匹配 special 不需要移动 pre
           }else{
               pre = next ;
           }
           next = next.getNext();
        }
        return head ;
    }
    public static DoubleNode deleteDoubleLinkedList(DoubleNode head , int special){
        DoubleNode next = head;
        DoubleNode pre = null ;
        while(next != null){
            if(next.getValue() == special){
                if(head == next){
                    head = next.getNext();
                }
                if(null != pre){
                    pre.setNext(next.getNext());
                }
                if(next.getNext() != null){
                    next.getNext().setPre(pre);
                }
            }else{
                pre = next ;
            }
            next = next.getNext();
        }
        return head ;
    }

    public static SingleNode deleteSingleLinkedListArrayList(SingleNode head , int special){
       List<Integer> list = new ArrayList<>();
       SingleNode pre = null ;
       SingleNode next = null ;
       while(head != null){
           if(special != head.getValue()){
               list.add(head.getValue());
           }
           head = head.getNext();
       }
       for(int i = 0 ; i < list.size() ; i++){
           next = new SingleNode();
           next.setValue(list.get(i));
           if(head == null){
               head = next ;
           }
           if(pre != null){
               pre.setNext(next);
           }
           pre = next ;
       }
       return head ;
    }

    public static int randomNode(AbsNode head){
        Random random = new Random();
        ArrayList<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.getValue());
            head = head.getNext();
        }
        int r = random.nextInt(list.size());
        return r >= list.size()? list.get(list.size() - 1):list.get(r) ;
    }

    public static void compareDoubleLinkedListDelete(int range , int size , int time){
        DoubleNode h1 = null ;
        DoubleNode h2 = null ;
        int special = 0 ;
        for(int i = 0 ; i < time ; i++){
            System.out.println("start... " + i);
            h1 = NumberComparator.fakeDoubleLinkedList(range , size);
            h2 = NumberComparator.copyDoubleLinkedList(h1);
            special = randomNode(h1);
            h1 = deleteDoubleLinkedList(h1 , special);
            h2 = deleteDoubleLinkedListArrayList(h2 , special);

            while(h1 != null && h2 != null){
                if(h1.getValue() != h2.getValue()){
                    System.out.println("not equal");
                    return;
                }
                h1 = h1.getNext() ;
                h2 = h2.getNext() ;
            }
            if(h1 != null || h2 != null){
                System.out.println("not equal");
            }
        }

    }

    private static DoubleNode deleteDoubleLinkedListArrayList(DoubleNode h, int special) {
        ArrayList<Integer> list = new ArrayList<>();
        DoubleNode head = null ;
        DoubleNode next = null ;
        DoubleNode pre = null ;
        while(h != null){
            if(special != h.getValue()){
                list.add(h.getValue());
            }
            h = h.getNext();
        }

        for(Integer node : list) {
            next = new DoubleNode();
            next.setValue(node);
            if(pre != null){
                pre.setNext(next);
            }
            if(head == null){
                head = next ;
            }
            next.setPre(pre);
            pre = next ;
            next = next.getNext();
        }
        return head;
    }

    public static void compareSingleLinkedListDelete(int range , int size , int time){
        SingleNode h1 = null ;
        SingleNode h2 = null ;
        SingleNode h3 = null ;
        int special = 0 ;
        for(int i = 0 ; i < time ; i++){
            h1 = NumberComparator.fakeSingleLinkedList(range , size);
            h2 = NumberComparator.copySingleLinkedList(h1);
            special = randomNode(h1);
            h1 = deleteSingleLinkedList(h1 , special);
            h2 = deleteSingleLinkedListArrayList(h2 , special);
            while(h1 != null && h2 != null){
                if(h1.getValue() != h2.getValue()){
                    System.out.println("not equal");
                    NumberComparator.forNodes(h3);
                    System.out.println();
                    NumberComparator.forNodes(h1);

                    return;
                }
                h1 = h1.getNext();
                h2 = h2.getNext();
            }
            if(h1 != null || h2 != null){
                System.out.println("not equal");
            }
        }
    }

    public static void main(String[] args) {
//        SingleNode head = NumberComparator.fakeSingleLinkedList(100, 10);
//        NumberComparator.forNodes(head);
//        System.out.println();
//        int special = head.getNext().getNext().getValue();
//        head = deleteSingleLinkedList(head , special);
//        NumberComparator.forNodes(head);
//        System.out.println();
//        head = deleteSingleLinkedListArrayList(head , head.getNext().getNext().getValue());
//        NumberComparator.forNodes(head);

//        DoubleNode head = NumberComparator.fakeDoubleLinkedList(100, 10);
//        NumberComparator.forNodes(head);
//        System.out.println("");
//        DoubleNode node = deleteDoubleLinkedList(head, head.getNext().getValue());
//        NumberComparator.forNodes(node);
//        compareSingleLinkedListDelete(100 , 12 , 10000);
        compareDoubleLinkedListDelete(200 , 14 , 1000);

    }
}
